package liecai_class.day05;

/**
 * 树的概念:
 *  树是一种非线性的数据结构 由n个节点组成的有限集合
 *  有一个特殊的节点称为根节点
 *  根节点下有0个或多个关联的子节点
 *  子节点下还可以有0个或多个有关联的子节点
 *  除了根节点外 每个节点有且只有一个父节点
 *  这样形成的数据结构称之为树
 *
 * 二叉树:
 *  二叉树是一种特殊的树
 *  要求每个节点最多只能有两个子节点
 *  左边的子节点称之为左子节点 右边的子节点称之为右子节点
 *  二叉树的子节点的顺序不能颠倒
 *
 *  满二叉树:
 *      除了叶子节点外 每个节点都有左右两个子节点 叶子节点都在同一层
 *      满二叉树的节点数是2的n次方-1，n是二叉树的层数
 *
 *  完全二叉树:
 *      除了最后一层外 其他层的节点数都达到最大值 最后一层的节点都集中在左边
 *
 *  二叉树的特点:
 *      1.二叉树的第i层最多有2的i-1次方个节点
 *      2.深度为k的二叉树最多有2的k次方-1个节点
 *
 *  二叉树的访问方式:
 *      A
 *      /\
 *     B  G
 *     /\  \
 *    C D   H
 *      /\
 *      E F
 *  前序遍历 - 根左右 - 先访问根节点 再访问左子节点 最后访问右子节点 A B C D E F G H
 *  中序遍历 - 左根右 - 先访问左子节点 再访问根节点 最后访问右子节点 C B E D F A G H
 *  后序遍历 - 左右根 - 先访问左子节点 再访问右子节点 最后访问根节点 C E F D B H G A
 *  层序遍历 - 从上到下 从左到右 - A B G C D H E F
 *
 *  二叉树的应用场景
 *    1.操作系统的文件系统
 *    2.数据库的索引
 *    3.表达式的计算
 *    4.游戏的AI
 *    5.路由协议
 *    6.解析XML
 *    7.解析JSON
 *    8.解析HTML
 *    9....
 */
public class Demo01 {
}
